package LeetCode;

import java.util.Arrays;

/**
 * @author Twelve
 */
public class quickSort
{
    public static void swap(int[] arr, int i, int j)
    {
        if (i != j)
        {
        //当i == j的时候，arr[i] = arr[i] ^ arr[j]会使arr[i/j]这里的值变为0，即arr[i]==arr[j]==0
        arr[i] ^= arr[j];
        arr[j] ^= arr[i];
        arr[i] ^= arr[j];
        }
    }

    public static int[] partition(int[] arr,int left,int right)
    {
        int indexNum=arr[right];
        int less=left-1;
        int more=right+1;
        int p=left;
        while(p<more)
        {
            if(arr[p]<indexNum)
            {
                less++;
                swap(arr,less,p);
                p++;
            }
            else if(arr[p]>indexNum)
            {
                more--;
                swap(arr,more,p);
            }
            else
            {
                p++;
            }
        }
        return new int[]{less,more};
    }

    public static void quicksort(int[] arr, int left, int right)
    {
        if(left<right)
        {
            if(right-left==1&&arr[left]>arr[right])
            {
                swap(arr,left,right);
                return;
            }
            swap(arr, (int)(left+Math.random()*(right-left)), right);
            System.out.println(arr[right]);

            int[] p = partition(arr, left, right);
            System.out.println(Arrays.toString(arr));

            quicksort(arr,left,p[0]);
            quicksort(arr,p[1],right);
        }
    }

    public static void main(String[] args)
    {
        int[] testArr = new int[(int) (Math.random() * 10) + 1];

        for(int i=0;i<testArr.length;i++)
        {
            testArr[i] = (int) (Math.random() * 100);
        }
        System.out.println(Arrays.toString(testArr));

        quicksort(testArr,0,testArr.length-1);
        System.out.println(Arrays.toString(testArr));
    }
}
